In computer science, there is a well-known basic dichotomy between whether a given quantity of code in a single program is executed at compilation time or at runtime. Whether individual steps in the code are executed at runtime or compilation time will have a significant effect on the overall efficiency of the code. Speaking very generally, to have certain operations occur at runtime makes for an appealingly simple code, but code that requires too many operations, such as table look-ups, at runtime will take orders of magnitude longer than an implementation which can perform some look-ups at compilation time. This is particularly true of library or middleware, that can be seen as providing a special-purpose language for doing certain kinds of operation (i.e., an image processing library can be seen as a special language for doing image processing). Most of the relative inefficiency comes from the inability of library code to make effective use of information available to users of the library; information that could be exploited at compilation time gets repeatedly rediscovered at runtime.
In order to overcome the problem of deciding whether the particular portions of a computer program should be executed at compilation time or runtime, one technique which has been developed recently is called "partial evaluation." An overview of partial evaluation can be found in the first three chapters of Ruf, "Topics in Online Partial Evaluation," (Ph.D. thesis, Stanford University, 1993). The Ruf dissertation basically describes an automatic program, called a "specializer," which operates in conjunction with a compiler: the specializer looks at codes submitted thereto, and makes an automatic inference, based on what information is known at a particular time, whether to "specialize" various portions of the program at partial evaluation time. Basically, if the specializer determines that it has enough information to specialize a particular input of the original program at partial evaluation time, and it judges that such specialization will be worthwhile, it does so. The overall output of the specializer is a new, specialized program which, when applied to any input satisfying the description, computes the same result as the original program. However, because the specialized program performed certain computations at partial evaluation time, the specialized program runs faster than the original program did.
Although a specializer as disclosed in the Ruf dissertation makes some progress in optimizing the execution of complicated programs, the practical applicability of partial evaluation has proven to be quite limited. It remains difficult to develop code that is highly efficient for purposes of partial evaluation, and all but impossible to make such code also easy to maintain.
The present invention takes an approach different from the attempt at total automation of partial evaluation, such as described in the Ruf dissertation. The present invention posits an arrangement whereby the programmer originating code has available to him certain software constructs which are read by a "partial evaluator," which is in effect a pre-compiler, which gives the programmer direct control over the execution time of different parts of the original program. The constructs of the present invention allow a programmer authoring a program to declare at individual call sites within the original program whether the code associated with a particular construct should be executed at runtime or at partial evaluation time.